我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode *one = head;
        ListNode *two = one->next;
        ListNode *three = two->next;
        two->next = one;
        one->next = swapPairs(three);
        return two;
    }
};

思路

以1->2->3->4举例

  1. 新建三个指针，one指向1，two指向2，three指向3
  2. 让two的下一个节点指向one，即2->1
  3. one的下一个节点指向函数swapPairs(three)返回的值
  4. 进入函数swapPairs(three)，此时新的one指向3，two指向4，three指向nullptr
  5. 让two的下一个节点指向one，即4->3
  6. one的下一个节点指向函数swapPairs(three)返回的值，此时由于three为空，所以返回的值它本身，即nullptr，所以3->nullptr
  7. 返回two，此时的two指向4，回到步骤3，所以步骤3中的one的下一个节点指向4，即1->4
  8. 完成2->1->4->3的两两交换
  9. 总结：递归，首先按顺序每两个节点组为一对，交换它们，最后从后向前依次把每一对连接起来（倒数第二个对的第二个节点指向倒数第一对的第一个节点，倒数第四对的第二个节点指向倒数第三对的第一个节点······）